package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2039 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int networkBecomesIdle(int[][] edges, int[] patience) {
            int n = patience.length;
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; ++i) {
                adj[i] = new ArrayList<Integer>();
            }
            boolean[] visit = new boolean[n];
            for (int[] v : edges) {
                adj[v[0]].add(v[1]);
                adj[v[1]].add(v[0]);
            }

            Queue<Integer> queue = new ArrayDeque<Integer>();
            queue.offer(0);
            visit[0] = true;
            int dist = 1;
            int ans = 0;

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int curr = queue.poll();
                    for (int v : adj[curr]) {
                        if (visit[v]) {
                            continue;
                        }
                        queue.offer(v);
                        int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
                        ans = Math.max(ans, time);
                        visit[v] = true;
                    }
                }
                dist++;
            }
            return ans;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC2039 an = new LC2039();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
